NJU 夏令营游记

总的来说还行，笔试做的很好，很流畅的就做了，机试做得稀烂。拿了三个奖状，一个参与奖（所有人都有哈哈），一个总分优秀（其实就是二等，8 ~ 24 名），一个是笔试优异（其实就是一等）。

笔试做到了全场 Rank 1！我很开心，但是其实笔试的题真没啥难的。大佬都看不上 NJU 所以肯定都没来，我就捡了个漏，好耶。

机试有一些阴间题也有好题。完全不适应 3 个小时 3 道题。两天都没上 100，导致最后总分就二等。实际上每天会做的题都有 150 分左右，但是就是没写出来或者忘了（呃呃）。

下面我会给每天的题意（简述），正解（如果知道）。

Day 1 笔试

T1

主要是你能不能读懂题，因为它不给任何术语定义。然后证明过程应该就不是很难了。我考的时候不知道同构是什么，尴尬了。

题意

设 $S_n$ 为长度为 $n$ 的置换构成的群， $A_n$ 为长度为 $n$ 的偶置换构成的群，证明 $S_n$ 和 $A_{n + 2}$ 同构。

解法

我还没仔细想，大伙来做吧。

T2

我切了，哈哈，简单吧。

题意

有一个无限集合 $S$ 上面定义了一个偏序。证明 $S$ 要么存在一个无限子集元素两两可比要么存在一个无限子集元素两两不可比。

解法

首先两两可比就是链，两两不可比就是反链。

反证，假如 $S$ 既没有无限长的链也没有无限长的反链。那么最长链和最长反链大小有限。

一个直觉的证明就是用 Dilworth 定理，最长反链等于最小链覆盖。用有限条有限长度的链就能覆盖整个集合，那么这个集合是有限集合，与题意矛盾。

但是这样做是假的。因为 Dilworth 不能用在无限集合上。改进也不难。设最长链大小是 $n$ 最长反链大小是 $m$ 。从 $S$ 中选一个大小是 $nm + 1$ 的子集（一定选得出来不然与题意矛盾），这里变成了有限集，再用 Dilworth。因为我用 $m$ 条长度为 $n$ 的链并不能覆盖 $nm + 1$ 个点，那么矛盾了。

T3

场上本来不会的，但是莫名其妙会了。其实我和通常解法不太一样。我想了个经典知名神奇函数就过了。

题意

设 $f$ 为一个定义在正实数集上的函数，并且函数值恒为正实数，有 $\lim_{x\to \infty} \dfrac {f(2x)}{f(x)} = 1$ 。

请问如下命题是否恒成立？如果是，请证明；如果不是，请给出对应的 $f$ 。

命题：对于任意正实数 $m$ ， $\lim_{x\to \infty} \dfrac {f(mx)}{f(x)} = 1$ 。

解法

不成立。

官方题解： $f(x) = \dfrac x {2^n} (2^n \leq x < 2^{n + 1})$ 。

场上的一个其他题解： $f(x) = \left\{\begin{aligned}&1, x = 2^n\\ &2, \text{otherwise}\end{aligned}\right.$ 。

我的做法： $f(x) = \left\{\begin{aligned}&1, x \in \mathbb{Q}\\ &2, \text{otherwise}\end{aligned}\right.$ 。

T4

比较简单一个题。

题意

给定一个二部图 $U\cup V$ ，保证 $U$ 中每个点的度数为 $2024$ 。定义一个“输入”为对 $V$ 中每个点赋非负整数权值的方案。对于一个输入， $U$ 中点的权值为它邻居的权值和除以 $2$ 的余数。定义“输出” $R$ 为 $U$ 中每个点的权值构成的序列。

证明：若有一个输入 $I$ 导致输出为 $R$ ，必有一个输入 $I'$ 也导致输出为 $R$ ，且 $I'$ 中 $0$ 的个数大于等于一半。

解法

记一个输入 $J$ 为 $I$ 中每个元素 $\bmod 2$ 的结果。那么 $J$ 的输出显然等于 $R$ 。

将 $J$ 中每个元素取反记作 $J'$ ，由于度数是偶数，所以 $J'$ 的输出容易证明也等于 $R$ 。

所以，只需令 $I' = \left\{\begin{aligned}&J, J \text{ 中 0 的个数大于 1 的个数}\\ &2, \text{otherwise}\end{aligned}\right.$ 即可。由于 $0$ 的个数始终大于等于其它数的个数，所以 $0$ 的个数是中大于等于一半。

Day 1 机试

T1

我为啥跳掉这题啊……

题意

给定 $n$ 个长度为 $m$ 的小写字母字符串，再给出一个极限距离 $d$ ，请问是否有一个长度为 $m$ 的任意字符串，满足到每个给定字符串的汉明距离不超过 $d$ 。如果有请输出这个串，否则输出 $-1$ 。

两个字符串 $s, t$ 的汉明距离 $\text{dis}(s, t)$ 定义为 $\big |\{i \mid s_i \neq t_i\}\big |$ 。

多测，最多 $10$ 组， $\sum n \leq 500, m\leq 10000, d\leq 5$ 。

解法

先删去所有字符串都相同的位置，若剩下的串长度大于 $nd$ 那就不合法直接输出 $-1$ 。

将第一个串作为初始答案串 $s$ 。比较答案串和其它串的汉明距离，如果都不超过 $d$ 就输出。否则找到任意一个 $t$ ，满足 $\text{dis}(s, t) > d$ ，改一下字符使 $t$ 合法。重复这一搜索过程。

注意到如果搜索层数超过 $d$ 那么距离第一个串就远了。所以搜索最多 $d + 1$ 层就行了。复杂度可以接受。

T2

致敬传奇题目 P4117，但我就是忘了（呃呃），导致只会 $O((n + V)\sqrt{n\log n})$ 。也有其它更优秀的做法，就不说了。

题意

给定一个序列 $a$ ，每次询问 $l, r, v$ ，求出以下过程的结果：
int f(int l, int r, int v)
{
int cnt = 0
for (int i = l; i <= r; i++) {
   if (v >= a[i]) {
       v -= a[i];
       cnt++;
   }
}
return cnt;
}
$0\leq n, q, a_i, v, \leq 2\times 10^5$ 。